home *** CD-ROM | disk | FTP | other *** search
/ InterCD 2000 September / september_2000.iso / intercd / root / ^Linux / WindowMaker / WINGs / bagarray.c next >
Encoding:
C/C++ Source or Header  |  2000-03-28  |  7.6 KB  |  420 lines
  1.  
  2.  
  3.  
  4.  
  5. #include <stdlib.h>
  6. #include <string.h>
  7.  
  8. #include "WUtil.h"
  9.  
  10. #if 0
  11.  
  12. typedef struct W_ArrayBag {
  13.     void **items;
  14.     int size;
  15.     int count;
  16.  
  17.     int base;
  18.     int first;
  19.     int last;
  20. } W_ArrayBag;
  21.  
  22.  
  23. static int    getItemCount(WMBag *bag);
  24. static int   appendBag(WMBag *bag, WMBag *appendedBag);
  25. static int   putInBag(WMBag *bag, void *item);
  26. static int   insertInBag(WMBag *bag, int index, void *item);
  27. static int   removeFromBag(WMBag *bag, void *item);
  28. static int   deleteFromBag(WMBag *bag, int index);
  29. static void*  getFromBag(WMBag *bag, int index);
  30. static int    firstInBag(WMBag *bag, void *item);
  31. static int    countInBag(WMBag *bag, void *item);
  32. static void*  replaceInBag(WMBag *bag, int index, void *item);
  33. static int   sortBag(WMBag *bag, int (*comparer)(const void*, const void*));
  34. static void   emptyBag(WMBag *bag);
  35. static void   freeBag(WMBag *bag);
  36. static void mapBag(WMBag *bag, void (*function)(void*, void*), void *data);
  37. static int    findInBag(WMBag *bag, int (*match)(void*));
  38. static void*  first(WMBag *bag, void **ptr);
  39. static void*  last(WMBag *bag, void **ptr);
  40. static void*  next(WMBag *bag, void **ptr);
  41. static void*  previous(WMBag *bag, void **ptr);
  42. static void*  iteratorAtIndex(WMBag *bag, int index, WMBagIterator *ptr);
  43. static int    indexForIterator(WMBag *bag, WMBagIterator ptr);
  44.  
  45.  
  46. static W_BagFunctions arrayFunctions = {
  47.     getItemCount,
  48.     appendBag,
  49.     putInBag,
  50.     insertInBag,
  51.     removeFromBag,
  52.     deleteFromBag,
  53.     deleteFromBag,
  54.     getFromBag,
  55.     firstInBag,
  56.     countInBag,
  57.     replaceInBag,
  58.     sortBag,
  59.     emptyBag,
  60.     freeBag,
  61.     mapBag,
  62.     findInBag,
  63.     first,
  64.     last,
  65.     next,
  66.     previous,
  67.     iteratorAtIndex,
  68.     indexForIterator
  69. };
  70.  
  71.  
  72. #define ARRAY ((W_ArrayBag*)bag->data)
  73.  
  74.  
  75. #define I2O(a, i) ((a)->base + i)
  76.  
  77.  
  78. WMBag*
  79. WMCreateArrayBagWithDestructor(int initialSize, void (*destructor)(void*))
  80. {
  81.     WMBag *bag;
  82.     W_ArrayBag *array;
  83.     int size;
  84.  
  85.     assert(0&&"array bag is not working");
  86.     bag = wmalloc(sizeof(WMBag));
  87.     
  88.     array = wmalloc(sizeof(W_ArrayBag));
  89.     
  90.     bag->data = array;
  91.  
  92.     array->items = wmalloc(sizeof(void*) * size);
  93.     array->size = size;
  94.     array->count = 0;
  95.     array->first = 0;
  96.     array->last = 0;
  97.     array->base = 0;
  98.  
  99.     bag->func = arrayFunctions;
  100.  
  101.     bag->destructor = destructor;
  102.  
  103.     return bag;
  104. }
  105.  
  106.  
  107. WMBag*
  108. WMCreateArrayBag(int initialSize)
  109. {
  110.     return WMCreateArrayBagWithDestructor(initialSize, NULL);
  111. }
  112.  
  113.  
  114. static int
  115. getItemCount(WMBag *bag)
  116. {
  117.     return ARRAY->count;
  118. }
  119.  
  120.  
  121. static int
  122. appendBag(WMBag *bag, WMBag *appendedBag)
  123. {
  124.     W_ArrayBag *array = (W_ArrayBag*)appendedBag->data;
  125.     int ok;
  126.     int i;
  127.  
  128.     for (i = array->first; i <= array->last; i++) {
  129.     if (array->items[array->base+i]) {
  130.         ok = putInBag(bag, array->items[array->base+i]);
  131.         if (!ok)
  132.         return 0;
  133.     }
  134.     }
  135.  
  136.     return 1;
  137. }
  138.  
  139.  
  140.  
  141. static int
  142. putInBag(WMBag *bag, void *item)
  143. {
  144.     return insertInBag(bag, ARRAY->last+1, item);
  145. }
  146.  
  147.  
  148.  
  149. static int
  150. insertInBag(WMBag *bag, int index, void *item)
  151. {
  152.     W_ArrayBag *array = ARRAY;
  153.     
  154.     if (I2O(array, index) >= array->size) {
  155.     array->size = WMAX(array->size + 16, I2O(array, index));
  156.     array->items = wrealloc(array->items, sizeof(void*) * array->size);
  157.     memset(array->items + I2O(array, array->last), 0,
  158.            sizeof(void*) * (array->size - I2O(array, array->last)));
  159.     }
  160.     
  161.     if (index > array->last) {
  162.     array->last = index;
  163.     } else if (index >= array->first) {
  164.     memmove(array->items + I2O(array, index),
  165.         array->items + (I2O(array, index) + 1), sizeof(void*));
  166.     array->last++;
  167.     } else {
  168.     memmove(array->items,
  169.         array->items + (abs(index) - array->base),
  170.         sizeof(void*) * (abs(index) - array->base));
  171.     memset(array->items, 0, sizeof(void*) * (abs(index) - array->base));
  172.     array->first = index;
  173.     array->base = abs(index);
  174.     }
  175.     
  176.     array->items[array->base + index] = item;
  177.     array->count++;
  178.     
  179.     return 1;
  180. }
  181.  
  182.  
  183. static int
  184. removeFromBag(WMBag *bag, void *item)
  185. {
  186.     int i;
  187.     W_ArrayBag *array = ARRAY;
  188.  
  189.     for (i = 0; i < array->count; i++) {
  190.     if (array->items[i] == item) {
  191.         if (bag->destructor)
  192.         bag->destructor(array->items[i]);
  193.         
  194.         memmove(&array->items[i], &array->items[i + 1],
  195.             (array->count - i - 1) * sizeof(void*));
  196.         array->count--;
  197.  
  198.         return 1;
  199.     }
  200.     }
  201.     
  202.     return 0;
  203. }
  204.  
  205.  
  206.  
  207. static int
  208. deleteFromBag(WMBag *bag, int index)
  209. {
  210.     W_ArrayBag *array = ARRAY;
  211.     
  212.     if (index < 0 || index >= array->count)
  213.     return 0;
  214.     
  215.     if (index < array->count-1) {
  216.     if (bag->destructor)
  217.         bag->destructor(array->items[index]);
  218.  
  219.     memmove(&array->items[index], &array->items[index + 1],
  220.         (array->count - index - 1) * sizeof(void*));
  221.     }
  222.     array->count--;
  223.     
  224.     return 1;
  225. }
  226.  
  227.  
  228. static void*
  229. getFromBag(WMBag *bag, int index)
  230. {
  231.     if (index < 0 || index >= ARRAY->count)
  232.     return NULL;
  233.  
  234.     return ARRAY->items[index];
  235. }
  236.  
  237.  
  238.  
  239. static int
  240. firstInBag(WMBag *bag, void *item)
  241. {
  242.     int j;
  243.     int count = ARRAY->count;
  244.     W_ArrayBag *array = ARRAY;
  245.     
  246.     for (j = 0; j < count; j++) {
  247.     if (array->items[j] == item)
  248.         return j;
  249.     }
  250.     return -1;
  251. }
  252.  
  253.  
  254.  
  255.  
  256. static int
  257. countInBag(WMBag *bag, void *item)
  258. {
  259.     int i, j;
  260.     int count = ARRAY->count;
  261.     W_ArrayBag *array = ARRAY;
  262.     
  263.     for (j = 0, i = 0; j < count; j++) {
  264.     if (array->items[j] == item)
  265.         i++;
  266.     }
  267.     return i;
  268. }
  269.  
  270.  
  271. static void*
  272. replaceInBag(WMBag *bag, int index, void *item)
  273. {
  274.     void *old;
  275.     
  276.     if (index < 0 || index >= ARRAY->count)
  277.     return NULL;
  278.     
  279.     old = ARRAY->items[index];
  280.  
  281.     ARRAY->items[index] = item;
  282.  
  283.     return old;
  284. }
  285.  
  286.  
  287. static int
  288. sortBag(WMBag *bag, int (*comparer)(const void*, const void*))
  289. {
  290.     qsort(ARRAY->items, ARRAY->count, sizeof(void*), comparer);
  291.     return 1;
  292. }
  293.  
  294.  
  295.  
  296. static void
  297. emptyBag(WMBag *bag)
  298. {
  299.     W_ArrayBag *array = ARRAY;
  300.     
  301.     if (bag->destructor) {
  302.     while (--array->count) {
  303.         bag->destructor(array->items[array->count]);
  304.     }
  305.     }
  306.     ARRAY->count=0;
  307. }
  308.  
  309.  
  310. static void
  311. freeBag(WMBag *bag)
  312. {
  313.     emptyBag(bag);
  314.  
  315.     wfree(ARRAY->items);
  316.     wfree(ARRAY);
  317.     wfree(bag);
  318. }
  319.  
  320.  
  321. static void
  322. mapBag(WMBag *bag, void (*function)(void *, void *), void *clientData)
  323. {
  324.     int i;
  325.     
  326.     for (i = 0; i < ARRAY->last; i++) {
  327.     if (ARRAY->items[i])
  328.         (*function)(ARRAY->items[i], clientData);
  329.     }
  330. }
  331.  
  332.  
  333. static int 
  334. findInBag(WMBag *bag, int (*match)(void*))
  335. {
  336.     int i;
  337.     
  338.     for (i = 0; i < ARRAY->last; i++) {
  339.     if ((*match)(ARRAY->items[i]))
  340.         return i;
  341.     }
  342.     
  343.     return -1;
  344. }
  345.  
  346.  
  347. static void*
  348. first(WMBag *bag, void **ptr)
  349. {
  350.     *ptr = NULL;
  351.  
  352.     if (ARRAY->count == 0)
  353.     return NULL;
  354.     
  355.     *(int**)ptr = 0;
  356.     return ARRAY->items[0];
  357. }
  358.  
  359.  
  360. static void*
  361. last(WMBag *bag, void **ptr)
  362. {
  363.     *ptr = NULL;
  364.     
  365.     if (ARRAY->count == 0)
  366.     return NULL;
  367.  
  368.     *(int*)ptr = ARRAY->count-1;
  369.  
  370.     return ARRAY->items[ARRAY->count-1];
  371. }
  372.  
  373.  
  374. static void*
  375. next(WMBag *bag, void **ptr)
  376. {
  377.     if (!*ptr)
  378.     return NULL;
  379.     
  380.     (*(int*)ptr)++;
  381.     if (*(int*)ptr >= ARRAY->count) {
  382.     *ptr = NULL;
  383.     return NULL;
  384.     }
  385.     
  386.     return ARRAY->items[*(int*)ptr];
  387. }
  388.  
  389.  
  390. static void*
  391. previous(WMBag *bag, void **ptr)
  392. {
  393.     if (!*ptr)
  394.     return NULL;
  395.     
  396.     (*(int*)ptr)--;
  397.     if (*(int*)ptr < 0) {
  398.     *ptr = NULL;
  399.     return NULL;
  400.     }
  401.     
  402.     return ARRAY->items[*(int*)ptr];
  403. }
  404.  
  405.  
  406.  
  407. static void* 
  408. iteratorAtIndex(WMBag *bag, int index, WMBagIterator *ptr)
  409. {
  410. }
  411.  
  412.  
  413. static int
  414. indexForIterator(WMBag *bag, WMBagIterator ptr)
  415. {
  416.     
  417. }
  418.  
  419. #endif
  420.